In multimedia processing systems, large amounts of data are processed in real time and typically stored in a memory between processing stages. For example, one or more processors read data from this memory, perform one or more processing steps, and write a result back into memory. Input/output devices ultimately perform the functions of sending the final result out of the system, for example to a display device and receiving initial data into the system.
Typically, the input and output functions require real-time data to be transferred at a specific rate. Any deviations from this rate can be noticeable as artifacts, such as audio clicks, video distortion, etc, or could cause connected subsystems to fail in other ways. In order to guarantee that data can be transferred in/out of the system at a fixed rate, the devices responsible for it must have certain guarantees for accessing the memory in terms of latency and bandwidth. Latency is the time between when a device requests access to memory for data read/write task and competing accessing the memory. The end of the latency period is the deadline by which the service request must be completed, and is sometimes referred to in the specifications as required-service-completion time. Duration is how long it takes to execute the request from start of service to completion. Bandwidth is the number of such accesses that can be performed per time unit.
The processing units have far less strict requirements, since they operate at a larger data granularity, such as entire video or audio frames, rather than individual pixels or samples. A short delay in memory access can be compensated for by a higher access rate later, thus still meeting any longer-term timing requirements.
Due to this nature, systems with both real-time and non-real-time access requirements typically operate by giving priority to the real-time devices and allowing the non-real-time devices access only when no real-time device has a request outstanding. Variants on this system may limit such priority to a maximum amount of time after which the non-real-time devices are serviced to prevent what is called ‘starvation’ of these lower-priority devices. A disadvantage of this approach is that the non-real-time devices suffer from decreased performance because they have to wait for access to the memory while the real-time devices go first. This happens because the scheduling algorithm used to control access has no knowledge of the service deadline requirements of the real-time requests.
One well-known method for scheduling real-time requests is the Earliest Deadline First algorithm (EDF). According to EDF, of all real-time requests waiting processing, the request having the earliest completion deadline receives the highest priority. EDF becomes problematic when there are both real-time and non-real-time clients in the system. Pure EDF cannot handle this, and the simple “extension” of this algorithm is to assign any leftover bandwidth to non-real-time clients. This is because priority is always given to real-time clients, even if handling a non-real-time client first would not endanger the deadlines of all real-time clients. When a non-real-time client has to wait for access, it is typically unable to continue operation until that access has been completed, forcing it to idle or stall, thus reducing its performance.
The original EDF is a fairly simple algorithm that probably can be implemented efficiently in software. When an extended EDF algorithm using software is made to include allocation of time to non-real-time requests, a processor must execute the extended EDF algorithm for priority allocation. This causes a substantial overhead of the processor time and reduces the portion of processor time available for the actual processing of all requests.
Consequently, a new scheduling method is needed for controlling access to any type of shared resource by multiple devices, the new method giving priority to non-real-time devices as long as the service deadlines for the outstanding real-time requests are met. That is, the new scheduling method should give priority to a non-real-time request even if a real-time request is pending when the non-real-time request can be performed without compromising the latency required by that real-time device. A hardware device is also needed for implementing the scheduling method, thus removing the scheduling load from the processor unit of the computing device. This frees up the processor unit.
In view of the foregoing, there is a need in the art for a new and improved method and device for extending existing scheduling algorithms to include requests by non-real-time devices and giving those devices priority if, and only if, all current and possible future real-time requests can still be executed on time.